//
// Created by zx208 on 2024/10/18.
//

#include "DoubleLinkedList.h"

// 头插法创建
DouLinkList Create_H_DL(DouLinkList head, int length){

    // 先创建头指针
    head = (DouLinkList) malloc(sizeof( DNode));
    head->next = NULL;
    head->prior = NULL;

    for (int i = 0; i < length; ++i) {
        DouLinkList p = (DouLinkList) malloc(sizeof( DNode));
        int data;
        scanf("%d", &data);
        p->data = data;

        p->next = head->next;
        // 注意！ 如果使用头插法创建双向链表时 头节点指向NULL时 此语句会出现段错误
        if(i != 0 ) head->next->prior = p;
        p->prior = head;
        head->next = p;
    }
    return head;
}

// 尾插法创建
DouLinkList Create_T_DL(DouLinkList head, int length){

    // 先创建头指针
    head = (DouLinkList) malloc(sizeof( DNode));
    head->next = NULL;
    head->prior = NULL;

    DouLinkList ptail = head; // 作用是工作指针
    for (int i = 0; i < length; ++i) {
        DouLinkList p = (DouLinkList) malloc(sizeof( DNode));
        int data;
        scanf("%d", &data);
        p->data = data;

        p->next = NULL;
        p->prior = ptail;
        ptail->next = p;
        ptail = p;
    }
    return head;
}

void Insert_DL(DouLinkList L, int pos, ElemType e){
    DouLinkList p = L;
    int i = 0;

    while(p->next && i < pos - 1 ) p = p->next, i++;

    DouLinkList pNew = (DouLinkList) malloc(sizeof( DouLinkList));
    pNew->data = e;

    // 这里类似头插法
    // 但是注意如果插入的位置是最后的位置时
    // 此时工作节点p->next为NULL NULL->prior将会报段错误
    // 所以在这里如果pos超过实际的位置时 一致放在链表最后
    pNew->next = p->next;
    if(p->next) p->next->prior = pNew;
    pNew->prior = p;
    p->next = pNew;
}

void Delete_DL(DouLinkList L, int pos, ElemType *e){
    DouLinkList p = L;
    int i = 0;

    while(p->next && i < pos - 1) p = p->next, i++;

    DouLinkList pfree = p->next;
    *e = pfree->data;

    p->next = pfree->next;
    pfree->next->prior = p;
    free(pfree);
    pfree = NULL;
}

void Print_DL(DouLinkList L){
    DNode *node = L->next;
    while(node){
        printf("%d ", node->data);
        node = node->next;
    }
}

int main(void){
    DouLinkList L = NULL;
    ElemType e = 0;
    L = Create_H_DL(L, 5);
    Insert_DL(L, 6, 10);
    Delete_DL(L, 1, &e);
    Print_DL(L);
    printf("\n%d", e);
    return 0;
}

// 1 2 3 4 5